package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href='https://leetcode.cn/problems/pascals-triangle/'>杨辉三角(Pascal's Triangle)</a>
 * <p>给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。</p>
 * <p>在「杨辉三角」中，每个数是它左上方和右上方的数的和。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1:
 *      输入: numRows = 5
 *      输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
 *                      1
 *                    1   1
 *                  1   2   1
 *                1   3   3   1
 *              1   4   6   4   1
 *
 * 示例 2:
 *      输入: numRows = 1
 *      输出: [[1]]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li> 1 <= numRows <= 30</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2022/5/18 16:20
 */
public class LC0118PascalsTriangle_S {

    static class Solution {
        public List<List<Integer>> generate(int numRows) {
            List<List<Integer>> ansList = new ArrayList<>(numRows);
            for (int i = 1; i <= numRows; i++) {
                // 第i行有i个数字
                List<Integer> rowList = new ArrayList<>(i);
                for (int j = 1; j <= i; j++) {
                    // 每行第一格和最后一格一定是1
                    if (j == 1 || j == i) {
                        rowList.add(1);
                    } else {
                        // 上一行：i-2；左上方：j-2，右上方：j-1
                        rowList.add(ansList.get(i - 2).get(j - 2) + ansList.get(i - 2).get(j - 1));
                    }
                }
                ansList.add(rowList);
            }
            return ansList;
        }
    }

}
